package com.xigua._高级数据结构或系统;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。
 * @date 2022/3/2317:38
 */
public class _440_字典序的第K小数字 {


    public static void main(String[] args) {
        findKthNumber(681692778, 351251360);
    }


    public static int findKthNumber(int n, int k) {
        int ans = 1;
        k--;
        while (k>0){
            int steps = getSteps(ans, n);
            if (steps>k){
                ans *=10;
                k--;
            }else {
                k -=steps;
                ans++;
            }
        }
        return ans;
    }

    public static int getSteps(int ans, long n) {
        long first = ans;
        long end = ans;
        int steps=0;
        while (first<=n){
            steps += Math.min(n,end)-first+1;
            first = first*10;
            end = end*10+9;
        }
        return steps;
    }

    public static int findKthNumber1(int n, int k) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            ans.add(i);
        }
        Collections.sort(ans,(o1, o2)->{
            return String.valueOf(o1).compareTo(String.valueOf(o2));
        });
        return ans.get(k-1);
    }

}


